When sensors measure data pertaining to a hidden stochastic (or, random) process in the physical world, such measurements are typically corrupted by noise and/or by uncertainty in the initial conditions. In order to usefully discern trends in the data and to make useful predictions with respect to future evolution of the process, it is necessary to estimate a “best guess” as to the true value of one or more random variables at one or more times during the course of the evolution of the process. (A more formal statement of the objective of filtering is provided below.) Much signal processing involves random processes, particularly, problems in remote sensing, air traffic surveillance, autonomous navigation, robotics and other control technologies, weather surveillance, and many others. The estimation of an entire posterior distribution of a random process (i.e., the distribution of the random variable conditional on the measurements performed) is referred to as the filtering problem.
In some cases, such as where noise is known to obey Gaussian distributions and where the systems are causal and time invariant, well-known solutions to the filtering problem may be applied. When an output variable may be characterized as a linear function of the hidden stochastic process, linear filtering techniques such as the Wiener filter or Kalman filter are applicable. In the nonlinear domain, filtering algorithms are analytically intractable and require some recursive process that may only be performed on a computer and require some form of approximation in order to be calculated in anywhere near real time.
In mathematical terms, the filtering problem can be stated in terms of the following stochastic differential equations (SDEs):dXt=a(Xt)dt+σBdBt,  (1a)dZtm=hm(Xt)dt+σWmdWtm,  (1b)where Xt is the state at time t, represented by a vector of real values, and Ztm is a (real) scalar-valued observation process for m=1, . . . , M, a(·), hm(·) are C1 (continuously differentiable) functions, and {Bt}, {Wtm}m=1M are mutually independent standard Wiener processes. By definition, Zt:=(Zt1, Zt2 . . . ZtM).
Eqn. 1a may be referred to as the “signal process equation,” while Eqn. 1b is “the observation process equation.” The notation employed in Eqns. 1a and 1b is that of stochastic differential equations interpreted in the Itōsense. Formally, “dXt=X(t+dt)−X(t),” and dBt˜N(0, dt) is an independent Gaussian increment with 0 mean and variance dt. Alternatively, by denoting
                             ″            ⁢      Y        :=                  ⅆ        Z                    ⅆ        t              ⁢      ,    ″  the observation equation may also be expressed as Yt=h(Xt)+σW{dot over (W)}t, where h(Xt)=(h1(Xt), h2(Xt), . . . , hM(Xt)). and {dot over (W)}t is the white noise process.
The objective of the filtering problem is to estimate the posterior distribution p* of Xt given the history t=:σ(Zs: s≦t). If a(·), h(·) are linear functions, the solution is given by the finite-dimensional Kalman filter. In the general case, however, a(·), h(·) are not limited to being linear functions. The theory of nonlinear filtering is described in the classic monograph Kallianapur et al., Stochastic filtering theory, vol. 13 of (1980), which is incorporated herein by reference. In the general case, the filter is infinite dimensional since it defines the evolution, in the space of probability measures, of {p*(·,t):t≧0}, and, for that reason alone, is not susceptible to analytical solution.
Various techniques known in the art for approximating non-linear filters are surveyed, for example, by Budhiraja et al., A survey of numerical methods for nonlinear filtering problems, Physica D, 230, pp. 27-36 (2007), incorporated herein by reference. The particle filter is a simulation-based approach to approximate the filtering task, whereby N stochastic processes {Xti: 1≦i≦N} are constructed. (The Xtis assume “real” values, in the mathematical sense.)
DEFINITION: Each of the N stochastic processes used in a simulation implementing a filter is called a “particle.” The value Xti is the state for the ith particle at time t.
For each time t, the empirical distribution (denoted p) formed by the “particle population” is used to approximate the posterior distribution. In sequential importance sampling, particles are generated according to their importance weight at every time step. Various approaches employ resampling or bootstrapping. Deficiencies of known techniques include high variance, which can be especially severe in cases where numerical instabilities arise. Sampling, additionally, imposes especially large computational and memory requirements. Thus, for the practical applications listed above, and for others, a more robust and efficient means for nonlinear filtering that avoids both resampling and bootstrapping is highly desirable.